COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A95.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 2, 1989}
\leftline {\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Primitive Recursion [Uses list convention]}

Let $\langle x, y\rangle$ be a non zero pairing function from $N \times N$
to $N$.  Let $\alpha$ and $\beta$ be the associated projections;
$\langle x, y\rangle↓\alpha = x$, $\langle x, y\rangle↓\beta = y$.  
We use $X↑{(n)}$ as an abbreviation for $x↓1, x↓2, \ldots, x↓n$.

\item{$\bullet$}  Z $( ) = 0$, the constant zero $(Z : N↑0 \rightarrow N)$
is a primitive recursive function (PRF).

\item{$\bullet$}  $S(x) = x + 1$, the successor function, is a PRF.

\item{$\bullet$}  $P↓{i,n} (X↑{(n)}) = x↓i$, for any fixed $1 \leq i \leq n$,
is a PRF.

\item{$\bullet$}  If $g↓1$, $g↓2, \ldots, g↓a (a\geq 0)$ are PRFs from $N↑b$
to $N (b \geq 0)$ and $f$ is a PRF from $N↑a$ to $N$, then $h = \hbox {Comp}
(f;\, g↓1, g↓2,\ldots, g↓a)$ is a PRF from $N↑b$ to $N$, defined by $h(X↑{(b)})
= f(g↓1(X↑{(b)})$, $g↓2(X↑{(b)}), \ldots, g↓a(X↑{(b)}))$.

\item{$\bullet$}  The pairing function is a PRF from $N↑2$ to $N$.

\item{$\bullet$}  The projections are PRFs from $N$ to $N$.

\item{$\bullet$}  If $f$ is a PRF from $N$ to $N$, then $f↑*(x, y) = f↑{(x)}(y)$ 
is a PRF from $N↑2$ to $N$.  Usually we will simply write $f↑{(x)}(y)$.

The PRFs are the smallest set of functions satisfying the above.

Letting $f = S$ in the definition of $f↑*$ gives $S↑{(x)}(y) = x + y$, a PRF.

If $h(X↑{(n)}) = f↓1(x↓i, x↓j, f↓2 (x↓k, x↓l))$, say, for constants
$1 \leq\{i, j, k, l\}\leq n$, where $f↓1$ and $f↓2$ are PRFs, we can expand the
definition to
$$\eqalign{g(X↑{(n)} & = f↓2\left (P↓{k,n} (X↑{(n)}), P↓{l,n}(X↑{(n)})\right )\cr
h(X↑{(n)}) & = f↓1\left (P↓{i,n}(X↑{(n)}), P↓{j,n}(X↑{(n)}), 
g(X↑{(n)})\right )\cr}$$
showing $h$ is a PRF.  Henceforth we use these definitions informally, as in
$h(x↓1, x↓2) = x↓1 + 2$ is a PRF, because $x↓1 + 2= S\left (S(x↓1)\right ) 
= S\left (S\left (P↓{12} (X↑{(2)})\right )\right )$.

If each $g↓i$ is a PRF, then $G$ defined by $G[X↑{(b)}] = \left [g↓1 [X↑{(b)}], 
\ldots, g↓a[X↑{(b)}]\right ]$ is a PRF.  ({\bf Drill:}  prove it).
In the case $a= b$, $G↑* (k, [X↑{(b)}])$ performs an arbitrary mapping on a
vector $k$ times, and is a PRF of $k$, $x↓1, x↓2, \ldots, x↓b$.  We use this
idea to show $x \dotminus 1$, which is $x-1$ for $x > 0$, 0 for $x = 0$, 
is a PRF.  Let
$G[u, v]  = [1, v + u]$.  Then
$$\eqalign{G↑0[0, 0] & = [0, 0]\cr
G↑1 [0, 0] & = [1, 0]\cr
G↑*(x, [1,0 ]) & = [1, x]\cr
G↑* (1 + x, [0, 0] & = [1, x]\cr
x \dotminus 1 & = G↑* (x, [ 0, 0])\beta\alpha.\cr}$$

To show multiplication is a PRF, let $G [u, v] = [u, v + u]$; then $G↑{(x)} 
[u, 0] = [ u, xu]$, and $xu = (G↑{(x)} [u, 0])\beta\alpha$.

The number of values of $i$ for which $0 \leq i < n$, $f[i] = 0$, is PR if
$f$ is; let $G[u, v] = (u + 1, v + (1 \dotminus f(u))$.  Then $G↑{(n)}[0, 0] =
[n, g(n)]$, etc.

Any function computable in ALGOL/PASCAL/FORTRAN using only known PRFs,
assignment, IF/FOR/DO statements, and compound statements, is a PRF.  The
use of WHILE, however, may lead to non-PRF functions.

[Replaces A61.Tex(154,phy]]
\bye